#include<iostream>
#include<vector>
using namespace std;

// 寻找插入点
int insertpoint(vector<int>& R, int k)
{
	int n = R.size();
	int low=0, high=n;
	
	// 查找区间至少含两个元素 
	while (low < high)
	{
		printf("[%d..%d]\n", low, high);
		int mid = (low+high) / 2;
		if (k <= R[mid])
			high=mid; // 在左区间中查找(含R[mid]) 
		else
			low=mid+1; // 在右区间中查找
	}
	
	printf("end:[%d..%d]\n", low, high);
	
	// 返回low
	return low;
}

int main()
{
	// 初始化数组
	vector<int> a = {1, 2, 2, 4};
	
	// 要插入的元素
	int k = 5;
	
	// 寻找插入点
	int i = insertpoint(a, k);
	
	// 打印
	printf("%d的插入点=%d\n", k, i);
	return 0;
}
